#include <stdio.h>

int lower_bound(int* nums, int numsSize, int target)
{
    //函数实现返回 满足第一个 >= target 的下标
    //开区间写法 (left,right)
    int left=-1;
    int right=numsSize;
    int mid=0;
    while(left<right-1)//区间不为空
    {
        mid=left+(right-left)/2;
        if(nums[mid]>=target)
        {
            right=mid; //该情况下 区间更新(left,mid)
        }
        else
        {
            left=mid; //该情况下 区间更新(mid,right)
        }
    }
    //退出循环 left+1=right
    //right 此时指向满足>=target的第一个下标
    return right;
}
int lower_bound_2(int* nums, int numsSize, int target)
{
        //此写法是闭区间写法
        int left=0;
        int right=numsSize-1;
        while(left<=right)
        {
            int mid=left+(right-left)/2;
            if(nums[mid]>=target)
            {
                right=mid-1; //[left,mid-1]
            }
            else
            {
                left=mid+1; //[mid+1,right]
            }
        }
        //退出循环此时 left=right+1
        //left 是第一个>=target 的下标
//5 7 7  8  8  10
//l   m       r
//.      l m  r
//.      l
//       r           
//       l
//     r
    return left;     
}
int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
    
    int start=lower_bound_2(nums,numsSize,target);
    int *ans=(int*)malloc(2*sizeof(int));
    *returnSize=2;
    if(start==numsSize || nums[start]!=target)
    {
        //1.数组是空
        //2.数组中不存在目标值
        ans[0]=-1;
        ans[1]=-1;
        return ans;
    }
        int end=lower_bound_2(nums,numsSize,target+1)-1;
        ans[0]=start;
        ans[1]=end;
        return ans;     
}